#include <stdio.h>
#include<stdlib.h>
#define maxsize 16

//直接插入排序
/***
 * 第一个元素看作有序，从第二个开始排序
 * i指向待排序
 * j用于扫描有序序列
 * 排序前判断比前一个大就继续下一次循环
 * 比前一个小就开是排序
 * 排序过程：先复制哨兵，倒叙比较哨兵和j所指，哨兵小，j所指后移；相等或大于时，复制到j+1位置
 ***/
typedef struct SeqList
{
    int data[maxsize];
    int length;
};

typedef struct LNode
{
    int data;
    LNode *next;
}LNode,*LinkList;

void PrintList(SeqList L){
    int i;
    for(i = 1;i<=L.length;i++)
        printf("data[%d] = %-5d",i,L.data[i]);

    return ;
}
void DreInsertList(SeqList &L){
    int i,j;
    for(i =2;i<=L.length;i++){
        if(L.data[i]<L.data[i-1]){
            L.data[0] = L.data[i];
            for(j = i-1;L.data[0]<L.data[j];--j)            //j--可以吗？
                L.data[j+1] = L.data[0];
        }
    }
    return ;
}

//冒泡排序
/***
 * 顺序表用比较次数作为阈值
 * 冒泡趟数+本趟比较次数 = 元素个数
 ***/
void BubbleSort_S(SeqList &L){
    int i,j,temp;
    for(i=1;i<=L.length-1;i++)
        for(j=1;j<=L.length-i;j++)
            temp = L.data[j] ;
            L.data[j+1] = temp;
            L.data[j] = L.data[j+1];
    
    return ;
}

void BubbleSort_L(LinkList &L){
    int i,j,length,temp;
    length = 0;
    LNode *p;
    p = L->next;
    while(p != NULL){
        length++;
        p = p->next;
    }
    if (length == 1)
        return;
    for(i = 1;i<=length-1;i++){
        for (j=1; j<= length-i; j++)
        {
            p=L->next;
            if (p->data < p->next->data)
            {
                temp = p->data;
                p->next->data = temp;
                p->data = p->next->data;
            }
            p = p->next;
        }
        
    }

}

